package NFA;


import Others.Edge;

import java.util.Scanner;
import java.util.Stack;

import static java.lang.System.exit;
import static java.lang.System.in;

public class CreateNFA {
    private String Regular_Expression;  //用户定义正则式
    private int kf = 0, ke = 0;   //状态初始和末端值
    private int c = 0;
    private boolean flag=true;

    //接收输入正规表达式，RegularExpression作为回传函数
    public CreateNFA(String regular_Expression) {
        Regular_Expression = regular_Expression;
        if (check_legal(Regular_Expression)) {
            System.out.println("正则表达式合格");
        } else if (!check_legal(Regular_Expression)) {
            exit(0);
        }

    }

    /**
     * 检测输入的正则表达式是否合法
     */
    boolean check_legal(String RegularExpression) {
        if (check_character(RegularExpression) && check_parenthesis(RegularExpression)) {
            return true;
        }
        return false;
    }

    /**
     * 检查输入的字符是否合适 () * | a~z A~Z
     * 合法返回true,非法返回false
     */
    boolean check_character(String RegularExpression) {
        int length = RegularExpression.length();
        for (int i = 0; i < length; i++) {
            char check = RegularExpression.charAt(i);
            if (is_letter(check))//小写和大写之间有5个字符，故不能连续判断
            {
                //System.out.println("字母 合法!");
            } else if (check == '(' || check == ')' || check == '*' || check == '|') {
                //System.out.println("操作符 合法");
            } else {
                System.out.println("含有不合法的字符!");
                System.out.println("请重新输入:");
                return false;
            }
        }
        return true;
    }

    /**
     * 先检查括号是否匹配
     * 合法返回true,非法返回false
     */
    boolean check_parenthesis(String RegularExpression) {
        int length = RegularExpression.length();
        char check[] = new char[length];
        for (int i = 0; i < length; i++) {
            check[i] = RegularExpression.charAt(i);     //将正则式复制进check数组中
        }

        Stack<Integer> STACK = new Stack<Integer>();    //创建栈
        for (int i = 0; i < length; i++) {
            if (check[i] == '(') {
                STACK.push(i);
            } else if (check[i] == ')') {
                if (STACK.empty()) {
                    System.out.println("有多余的右括号");   //暂时不记录匹配位置location
                    System.out.println("请重新输入:");
                    return false;
                } else {
                    STACK.pop();
                }
            }
        }
        if (!STACK.empty()) {
            //暂时不记录匹配位置location
            System.out.println("有多余的左括号");
            System.out.println("请重新输入:");
            return false;
        }
        return true;
    }

    /**
     * 检测是否是字母
     * 是返回true,否则false
     */
    boolean is_letter(char check) {
        if (check >= 'a' && check <= 'z' || check >= 'A' && check <= 'Z') {
            return true;
        }
        return false;
    }

    //消除重复字符
    char [] cleanRepeat(char[] oldArr){
        int count=0;
        for (int i=0;i<oldArr.length-1;i++){
            for (int j=i+1;j<oldArr.length;j++){
                if (oldArr[i]==oldArr[j]){
                    count++;
                    break;
                }
            }
        }
        char[] newArr=new char[oldArr.length-count];
        int index=0;
        for (int i=0;i<oldArr.length;i++){
            boolean flag=false;
            char temp=oldArr[i];
            for (int j=0;j<newArr.length;j++){
                if (newArr[j]==temp){
                    flag=true;
                    break;
                }
            }
            if (flag==false){
                newArr[index++]=temp;
            }
        }
        return newArr;
    }


    //处理 a
    NFA do_a(char element) {
        NFA NewNFA = new NFA();
        NewNFA.setCount(0);    //设置初始结点个数为0

        //构建边
        Edge NewEdge = new Edge();
        NewEdge.setFirstSpot(ke++);
        NewEdge.setRearSpot(ke);
        int State[] = new int[2];    //存储状态
        NewEdge.setCh(element);
        for (int i = 0; i < 2; i++) {
            State[i] = kf + i;
        }
        NewNFA.setCount(ke - kf);    //设置结点个数

        //设置move转移函数
        Edge move = new Edge();
        move.setCh(element);
        move.setFirstSpot(State[0]);
        move.setRearSpot(State[1]);
        Edge Move[] = new Edge[1];
        Move[0] = move;

        //设置字符集
        char E[] = new char[1];
        E[0] = element;

        //设置新NFA
        NewNFA.setState(State);
        NewNFA.setMove(Move);
        NewNFA.setE(E);
        NewNFA.setS0(kf);
        NewNFA.setF(ke);
        NewNFA.setFirst(NewNFA.getS0());
        NewNFA.setRear(NewNFA.getF());

        kf = ++ke;

        return NewNFA;
    }


    //处理 a*
    NFA do_Star(NFA old_Nfa){
        NFA new_Nfa=new NFA();
        Edge edge[]=new Edge[4];
        for (int i=0;i<4;i++){
            edge[i]=new Edge();
        }

        //初始化新结点
        edge[0].setFirstSpot(kf);
        edge[0].setRearSpot(old_Nfa.getFirst());
        edge[0].setCh('#');
        edge[1].setFirstSpot(old_Nfa.getRear());
        edge[1].setRearSpot(kf+1);
        edge[1].setCh('#');
        edge[2].setFirstSpot(edge[0].getFirstSpot());
        edge[2].setRearSpot(edge[1].getRearSpot());
        edge[2].setCh('#');
        edge[3].setFirstSpot(edge[1].getFirstSpot());
        edge[3].setRearSpot(edge[0].getRearSpot());
        edge[3].setCh('#');

        //设置State状态集
        int State[]=new int[old_Nfa.getState().length+2];
        for (int i=0;i<old_Nfa.getState().length+2;i++){
            if (i<old_Nfa.getState().length){
                State[i]=old_Nfa.getState()[i];
            }else {
                State[i]=kf+(i-old_Nfa.getState().length);
            }
        }

        //设置move转移函数
        int m_length=old_Nfa.getMove().length+4;
        Edge move[]=new Edge[m_length];
        for (int i=0;i<m_length;i++){
            if (i<old_Nfa.getMove().length){
                move[i]=old_Nfa.getMove()[i];
            }else {
                move[i]=edge[i-old_Nfa.getMove().length];
            }
        }

        //设置新NFA

        new_Nfa.setState(State);
        new_Nfa.setMove(move);
        new_Nfa.setE(old_Nfa.getE());
        new_Nfa.setF(edge[1].getRearSpot());
        new_Nfa.setFirst(edge[0].getFirstSpot());
        new_Nfa.setRear(edge[1].getRearSpot());

        kf=kf+2;
        ke=ke+2;   //更新结点数指针

        return new_Nfa;
    }

    //处理 ab
    NFA do_join(NFA Left, NFA Right){
        NFA NewNFA = new NFA();
//        Edge new_right[]=new Edge[1];
//        new_right[0]=new Edge();
//        new_right[0].setFirstSpot(Left.getF());
//        new_right[0].setRearSpot(Left.getF()+1);
//        new_right[0].setCh(Right.getMove()[0].getCh());
//        int new_state[]=new int[1];
//        new_state[0]=Right.getState()[0];
//        Right.setMove(new_right);
//        Right.setS0(Right.getMove()[0].getRearSpot());
//        Right.setF(Right.getS0());
//        Right.setState(new_state);

        //构建边
        Edge NewEdge = new Edge();
        NewEdge.setFirstSpot(Left.getRear());
        NewEdge.setRearSpot(Right.getFirst());
        NewEdge.setCh('#');

        //设置State状态集
        int State[] = new int[Left.getState().length+ Right.getState().length];
        for (int i = 0; i<Left.getState().length+ Right.getState().length;i++){
            if(i<Left.getState().length){
                State[i]=Left.getState()[i];
            }else {
                State[i]=Right.getState()[i-Left.getState().length];
            }
        }

        //设置move转移函数
        int m_length=Left.getMove().length+Right.getMove().length+1;
        Edge move[] = new Edge[m_length];
        for (int i=0;i<m_length;i++){
            if(i<Left.getMove().length){
                move[i]=Left.getMove()[i];
            }else if(i== Left.getMove().length){
                move[i]=NewEdge;
            }else {
                move[i]= Right.getMove()[i-Left.getMove().length-1];
            }
        }

        //设置E字符集
            int E_Length = Left.getE().length +Right.getE().length;
        char Element[] = new char[E_Length];
        for (int i = 0; i < E_Length; i++) {
            if (i < Left.getE().length) {
                    Element[i] = Left.getE()[i];

            } else {
                Element[i]=Right.getE()[i-Left.getE().length];
            }
        }
        char newElement[]=cleanRepeat(Element);


        //设置新NFA
        NewNFA.setState(State);
        NewNFA.setMove(move);
        NewNFA.setE(newElement);
        NewNFA.setF(Right.getF());
        NewNFA.setFirst(Left.getFirst());
        NewNFA.setRear(Right.getRear());

        return NewNFA;
    }

    //处理 a|b
    NFA do_unit(NFA Left, NFA Right) {
        NFA NewNFA = new NFA();
        NewNFA.setCount(Left.getCount() + Right.getCount() + 1);  //设置新NFA结点个数

        //设置新结点
        Edge edge[] = new Edge[4];
        for (int i = 0; i < 4; i++) {
            edge[i] = new Edge();
        }

        edge[0].setRearSpot(Left.getFirst());
        edge[0].setFirstSpot(kf);
        edge[1].setFirstSpot(kf);
        edge[1].setRearSpot(Right.getFirst());
        edge[2].setFirstSpot(Left.getRear());
        edge[2].setRearSpot(kf + 1);
        edge[3].setFirstSpot(Right.getRear());
        edge[3].setRearSpot(kf + 1);
        edge[0].setCh('#');
        edge[1].setCh('#');
        edge[2].setCh('#');
        edge[3].setCh('#');

        //设置State状态集
        int State[] = new int[kf + 2];
        for (int i = 0; i < kf + 2; i++) {
            State[i] = i;
        }

        //设置E字符集
        int E_Length = Left.getE().length + Right.getE().length;
        char Element[] = new char[E_Length];
        for (int i = 0; i < E_Length; i++) {
            if (i < Left.getE().length) {
                for (int k_L = 0; k_L < Left.getE().length; k_L++) {
                    Element[i] = Left.getE()[k_L];
                }
            } else {
                for (int k_r = i - Left.getE().length; k_r < Right.getE().length; k_r++) {
                    Element[i] = Right.getE()[k_r];
                }
            }
        }
        char newElement[]=cleanRepeat(Element);

        //设置move函数
        int m_length = 4 + Left.getMove().length + Right.getMove().length;
        Edge NewEdge[] = new Edge[4 + Left.getMove().length + Right.getMove().length];
        for (int i = 0; i < m_length; i++) {
            if (i < Left.getMove().length) {
                NewEdge[i] = new Edge();
                NewEdge[i] = Left.getMove()[i];
            } else if (i < Left.getMove().length + Right.getMove().length) {
                {
                    NewEdge[i] = new Edge();
                    NewEdge[i] = Right.getMove()[i - Left.getMove().length];
                }
            } else {
                NewEdge[i] = new Edge();
                NewEdge[i] = edge[i - (Left.getMove().length + Right.getMove().length)];
            }
        }

        //设置新NFA
        NewNFA.setState(State);
        NewNFA.setE(newElement);
        NewNFA.setMove(NewEdge);
        NewNFA.setF(edge[3].getRearSpot());
        NewNFA.setCount(NewNFA.getState().length);
        NewNFA.setFirst(edge[0].getFirstSpot());
        NewNFA.setRear(edge[3].getRearSpot());

        ke = ke + 2;
        kf = kf + 2;   //更新初态、终态指针

        return NewNFA;
    }


    /**
     * 表达式转NFA处理函数,返回最终的NFA结合
     */
    public void transfer_NFA(String RegularExpression) {
//        //添加“+”，便于转后缀表达式
        RegularExpression = add_join_symbol(RegularExpression);
//        //中缀转后缀
        RegularExpression = postfix(RegularExpression);

        int length = RegularExpression.length();
        char element;
        NFA Nfa, Left, Right;
        Stack<NFA> STACK = new Stack<NFA>();

        for (int i = 0; i < length; i++) {
            element = RegularExpression.charAt(i);
            if (flag==true){
                switch (element) {
                    case '|':
                        Right = STACK.peek();
                        STACK.pop();
                        Left = STACK.peek();
                        STACK.pop();
                        Nfa = do_unit(Left, Right);
                        STACK.push(Nfa);
                        break;
                    case '+':
                        Right = STACK.peek();
                        STACK.pop();
                        Left = STACK.peek();
                        STACK.pop();
                        Nfa = do_join(Left, Right);
                        STACK.push(Nfa);
                        break;
                    case '*':
                        Left = STACK.peek();
                        STACK.pop();
                        Nfa = do_Star(Left);
                        STACK.push(Nfa);
                        break;
                    default:
                        Nfa = do_a(element);
                        STACK.push(Nfa);
                }
            }
        }

        System.out.println("处理完毕!");
        Nfa = STACK.peek();
        STACK.pop();

        Display(Nfa);
    }


    /**
     * 显示NFA
     */
    void Display(NFA Nfa) {
        System.out.print("状态集： ");
        for (int i = 0; i < Nfa.getState().length; i++) {
            System.out.print(Nfa.getState()[i] + " ");
        }
        System.out.println();

        System.out.print("合法字符集： ");
        for (int i = 0; i < Nfa.getE().length; i++) {
            System.out.print(Nfa.getE()[i] + " ");
        }
        System.out.println();

        System.out.println("起点：" + Nfa.getS0() + " ; 终点：" + Nfa.getF());

        System.out.println("move 函数（ 共" + Nfa.getMove().length + " 个 ）：");
        for (int i = 0; i < Nfa.getMove().length; i++) {
            System.out.println("move(" + Nfa.getMove()[i].getFirstSpot() + " , " + Nfa.getMove()[i].getCh() + ") = " + Nfa.getMove()[i].getRearSpot());
        }
    }

    /**
     * 添加交操作符“+”，便于中缀转后缀表达式
     * 例如 abb->a+b+b
     */
    String add_join_symbol(String add_string) {
        int length = add_string.length();
        int return_string_length = 0;
        char return_string[] = new char[2 * length];//最多是两倍
        char first, second;
        for (int i = 0; i < length - 1; i++) {
            first = add_string.charAt(i);
            second = add_string.charAt(i + 1);

            return_string[return_string_length++] = first;
            //若第二个是字母、第一个不是'('、'|'都要添加
            if (first != '(' && first != '|' && is_letter(second)) {
                return_string[return_string_length++] = '+';
            }
            //若第二个是'(',第一个不是'|'、'(',也要加
            else if (second == '(' && first != '|' && first != '(') {
                return_string[return_string_length++] = '+';
            }
        }
        //将最后一个字符写入
        second = add_string.charAt(length - 1);
        return_string[return_string_length++] = second;
        char return_string_new[] = new char[return_string_length];
        for (int i = 0; i < return_string_new.length; i++) {
            return_string_new[i] = return_string[i];
        }
        String str = new String(return_string_new);
        System.out.println("加'+'后的表达式：" + str);
        return str;
    }


    /**
     * 中缀表达式转后缀表达式
     */
    String postfix(String e) {
        //设定e的最后一个符号式“#”，而其“#”一开始先放在栈s的栈底
        e = e + "#";

        Stack<Character> s = new Stack<>();
        char ch = '#', ch1, op;
        s.push(ch);
        //读一个字符
        String out_string = "";
        int read_location = 0;
        ch = e.charAt(read_location++);
        while (!s.empty()) {
            if (is_letter(ch)) {
                out_string = out_string + ch;
                //cout<<ch;
                ch = e.charAt(read_location++);
            } else {
                //cout<<"输出操作符："<<ch<<endl;
                ch1 = s.peek();

                if (isp(ch1) < icp(ch) && isp(ch1) != -1 && icp(ch) != -1) {
                    s.push(ch);
                    //cout<<"压栈"<<ch<<"  读取下一个"<<endl;
                    ch = e.charAt(read_location++);
                } else if (isp(ch1) > icp(ch) && isp(ch1) != -1 && icp(ch) != -1) {
                    op = s.peek();
                    s.pop();
                    //cout<<"退栈"<<op<<" 添加到输出字符串"<<endl;
                    out_string = out_string + op;
                    //cout<<op;
                } else {
                    op = s.peek();
                    s.pop();
                    //cout<<"退栈"<<op<<"  但不添加到输入字符串"<<endl;

                    if (op == '(') {
                        ch = e.charAt(read_location++);
                    }
                }
            }
        }
        System.out.println("后缀表达式：" + out_string);
        return out_string;
    }


    /*
优先级表：
	 #	(	*	|	+	)
isp  0	1	7	5	3	8
icp	 0	8	6	4	2	1
*/
//in stack priority  栈内优先级
    int isp(char c) {
        switch (c) {
            case '#':
                return 0;
            case '(':
                return 1;
            case '*':
                return 7;
            case '|':
                return 5;
            case '+':
                return 3;
            case ')':
                return 8;
        }
        //若走到这一步，说明出错了
        System.out.println("ERROR!");
        return -1;
    }

    //in coming priority 栈外优先级
    int icp(char c) {
        switch (c) {
            case '#':
                return 0;
            case '(':
                return 8;
            case '*':
                return 6;
            case '|':
                return 4;
            case '+':
                return 2;
            case ')':
                return 1;
        }
        //若走到这一步，说明出错了
        System.out.println("ERROR!");
        return -1;
    }
}

//class test {
//    public static void main(String[] args) throws InterruptedException{
//        String Regular_Expression;   //用户定义正则式
//        int Regular_Expression_length;  //正则式长度
//
//        Scanner scanner = new Scanner(System.in);
//        System.out.println("请输入正则表达式：  （操作符：() * |;字符集：a~z A~Z）");
//        Regular_Expression=scanner.nextLine();
//        Regular_Expression_length=Regular_Expression.length();
//
//        CreateNFA nfa=new CreateNFA(Regular_Expression);   //创建NFA
//        nfa.transfer_NFA(Regular_Expression);
//    }
//}

